﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace UndirectedGraphs
{
    public class DepthFirstSearch
    {
        private bool[] marked;       // marked[v] = is there an s-v path?
        private int count;           // number of vertices connected to s

        /**
     * Computes the vertices in graph <tt>G</tt> that are
     * connected to the source vertex <tt>s</tt>.
     * @param G the graph
     * @param s the source vertex
     */

        public DepthFirstSearch(Graph G, int s)
        {
            marked = new bool[G.V()];
            dfs(G, s);
        }

        // depth first search from v
        private void dfs(Graph G, int v) {
            count++;
            marked[v] = true;
            foreach (int w in G.adj(v))
            {
                if (!marked[w]) {
                    dfs(G, w);
                }
            }        
        }

        public bool is_marked(int v)
        {
            return marked[v];
        }

        public int return_count()
        {
            return count;
        }
    }
}
